package leetcode_core.leetcode_1;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

public class FindTargetSumWaysBackTrack {
    private int[] op = new int[]{1,-1};
    private Map<String,Integer> memo;
    /**
     * 回溯算法:
     * @param nums
     * @param i:代表的是目前要对哪个数字进行加减的置换
     * @param rest:代表的是距离target的程度,当为0的时候,意味着找到了一组可行的解决方案
     */
    private int backtrack(int[] nums,int i,int rest){
        if(i==nums.length){
            if(rest == 0){
                return 1;
            }
            return 0;
        }
        String key = i+","+rest;
        if(memo.containsKey(key)){
            return memo.get(key);
        }
        int sum = 0;
        for(int j = 0;j< op.length;j++){
            rest += op[j]*nums[i];
            sum+= backtrack(nums,i+1,rest);
            rest -= op[j]*nums[i];
        }
        memo.put(key,sum);
        return sum;
    }



    public int findTargetSumWays(int[] nums, int target) {
        memo = new HashMap<>();
        return backtrack(nums,0,target);
    }

    @Test
    public void testCaseOne(){
        System.out.println(findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3));
    }
    @Test
    public void testCaseTwo(){
        System.out.println(findTargetSumWays(new int[]{1}, 1));
    }


}
